On Longest Repeat Queries Using GPU

摘要

Repeat finding in strings has important applications in subfields such ascomputational biology. The challenge of finding the longest repeats coveringparticular string positions was recently proposed and solved by \.{I}leri etal., using a total of the optimal $O(n)$ time and space, where $n$ is thestring size. However, their solution can only find the \emph{leftmost} longestrepeat for each of the $n$ string position. It is also not known how toparallelize their solution. In this paper, we propose a new solution forlongest repeat finding, which although is theoretically suboptimal in time butis conceptually simpler and works faster and uses less memory space in practicethan the optimal solution. Further, our solution can find \emph{all} longestrepeats of every string position, while still maintaining a faster processingspeed and less memory space usage. Moreover, our solution is\emph{parallelizable} in the shared memory architecture (SMA), enabling it totake advantage of the modern multi-processor computing platforms such as thegeneral-purpose graphics processing units (GPU). We have implemented both thesequential and parallel versions of our solution. Experiments with bothbiological and non-biological data show that our sequential and parallelsolutions are faster than the optimal solution by a factor of 2--3.5 and 6--14,respectively, and use less memory space.